A packet switching network comprises an array of packet switches interconnected by trunks. Typically, a packet switch comprises a set of inputs which receive arriving packets via a set of incoming trunks and a set of outputs which are connected to a set of outgoing trunks via which packets depart the switch.
The inputs and outputs are connected by a switch fabric. Illustratively, the switch fabric is a self-routing switch fabric. A self-routing switch fabric typically comprises an array of nodes organized into stages. At each node routing decisions are made based on an address contained in the header of the packet being routed. Typically, such self-routing networks are synchronous so that packets arrive simultaneously at the inputs in intervals of time known as time slots.
The most commonly used self-routing switching fabric utilizes a Batcher network and a banyan network. A banyan network is a self-routing network which can route a packet from any input to any output based on an address contained in the packet header. However, the banyan network suffers from internal packet collisions. To eliminate internal collisions in a banyan network, the packets in any time slot are presented to the inputs of the banyan network in increasing or decreasing order according to destination address. In addition, the packets received at the inputs to the banyan network should be concentrated, i.e., there should be no inactive input lines to the banyan network in between active input lines to the banyan network in any particular time slot. Thus, the banyan network is usually preceded by a Batcher network which sorts arriving packets according to destination address. The sorted packets are then routed to the desired outputs as indicated by their addresses by the banyan network. Thus, the combined Batcher-banyan network provides a full connection, internally collisionless switch fabric. To insure that the packets arriving at the banyan network in a time slot are concentrated, a concentrator network may be located between the Batcher network and the banyan network.
For a banyan network which forms part of a Batcher-banyan network to be non-blocking (i.e. suffer no internal collision), the Batcher outputs and the banyan inputs are connected with a pattern known as a perfect shuffle. Consider a situation where there are 64 interconnections between the Batcher network and the banyan network. Assume the Batcher outputs are numbered 1 to 64 and that the banyan inputs are also numbered 1 to 64. The first half of the Batcher outputs (1-32) are connected to the odd numbered banyan inputs 1,3 . . . 63. The second half of the Batcher outputs (33-64) are connected to the even numbered banyan inputs 2,4 . . . 64. This is like a perfect shuffle of the two halves of a deck of playing cards.
While switch fabrics based on the Batcher-banyan network do not suffer from internal collisions, they do suffer from external collisions. An external collision occurs when two or more packets destined for the same output are simultaneously presented at the inputs of the Batcher-banyan network.
Several algorithms have been devised for resolving such output port conflicts so as to eliminate external collisions in a Batcher-banyan network. These algorithms are
1. Recirculation Algorithm: This algorithm feeds blocked packets back to the inputs for re-entry at the next time slot. (See e.g., Huang, A. and Knauer, S., Starlite: A Wideband Digital Switch, Proceeding of Globecom 84, pp. 121-125).
2. Three Phase Algorithm: This algorithm is also a feedback scheme. Each input sends a probing header for arbitration in phase 1. The inputs then receive a positive or negative acknowledgement back from the outputs in phase 2. The actual transmission of the winning packets, i.e., those who receive positive acknowledgements, takes place in phase 3. (See e.g., Hui, Y. N. J. and Arthurs, E., A Broadband Packet Switch for Integrated Transport, IEEE Journal on Selected Areas in Communications, Vol. 5, No. 8, October 1987, pp. 1264-1273; see also T. T. Lee et al, "The Architecture for a Multicast Broadband Packet Switch", Proceedings of Infocom 1988, pp. 1-8 which describes a three phase algorithm in which only a Batcher network is required for arbitration).
3. Ring Reservation Algorithm: This is a token passing scheme. At the beginning of a time slot, a clear token is issued by a token generator. The token has an N-bit field to indicate the availability of each of N outputs. The token is circulated around a ring connecting input ports associated with each of the packet switch inputs. When the token arrives at a particular input port, the packet at the head of a queue at the particular input port will make a reservation by writing a logic "1" into the bit position of the token corresponding to the desired output, if the desired output has not been reserved by a previous input port on the ring. If the intended output is successfully reserved, the packet is transmitted during the next time slot. The reservation cycle and transmission cycle can be overlapped to minimize the overhead. (See, e.g., Bingham B. and Bussey H., Reservation-Based Contention Resolution Mechanism for Batcher-Banyan Packet Switches, Electronics Letters, 23rd, Vol. 24, No. 13, June 1988, pp. 772-773; see also B. Binghan et al, U.S. Pat. No. 4,761,780).
Any of the three algorithms mentioned above has the potential to resolve output port conflicts and eliminate external collisions for a switch fabric based on a Batcher-banyan network.
A packet switch which serves as a central office for a broadband telecommunications network will require approximately 10,000 inputs and outputs. Such very large packet switches, when implemented using very large Batcher-banyan switch fabrics, have a number of significant problems. First, the non-blocking property of the Batcher-banyan switch fabric requires that the whole set of input packets (i.e. the set of packets arriving at the inputs of the switch fabric during one time slot) be synchronized at every stage of the switch fabric. For a switch with 10,000 inputs, this means synchronizing up to 10,000 packets within a network of about 100 stages. A second problem with a very large packet switch is the physical limitations on the size of the VLSI chips and the complexity of the interconnection wiring between the chips. A third problem with very large packet switches relates to reliability and maintainability. It is clear that smaller switch fabrics are easier to develop, to test, to maintain, and to replace.
A number of approaches have been developed for modularizing very large switches (see e.g., C. Clos, "A Study of Non-Blocking Switching Networks", Bell System Technical Journal, vol. 32, 1953, pp. 406-424; D. R. Spears, "Broadband ISDN Switching Capability From A Service Perspective", IEEE Journal of Selected Areas in Comm., Vol. SAC-5, No. 8, October 1987, pp. 1222-1230). Conventional approaches to modularizing very large Batcher-banyan switch fabrics have not proven to be successful in solving the above-identified problems. When modularized in the conventional manner, very large Batcher-banyan switch fabrics are formed from relatively small Batcher-banyan modules which are grouped in stages. One output of each Batcher-banyan module in one stage is connected to each Batcher-banyan module in the next stage. This provides full interconnectivity between all the inputs and all the outputs of the very large packet switch. However, in order for packets arriving at the switch in a particular time slot to be routed from particular inputs to particular outputs, the packets must pass through a plurality of the relatively small Batcher-banyan modules in a plurality of stages. When this type of modular architecture is utilized, it is possible to independently synchronize the individual Batcher-banyan modules only if buffers are utilized between the stages. Without such buffers all of the modules have to be globally synchronized. Furthermore, the conventional modular architecture described above requires complex interconnections between the stages of Batcher-banyan modules. In addition, because a packet must pass through more than one of the Batcher-banyan modules to be routed from a particular input to a particular output, if one of the Batcher-banyan modules fails, the switch as a whole no longer operates properly. Still another problem with the conventional modular architecture relates to conflict resolution. Because the modules do not operate independently of each other, and because each packet has to pass through a plurality of modules in a plurality of stages, conflict resolution is very difficult. In particular, conflict resolution has to be performed at every Batcher-banyan module, which conflict resolution also requires buffers internally between the stages. Accordingly, such a conventional modular architecture is not suitable for implementing a very high-speed packet switch.
To overcome the above-described problems which are characteristic of very large packet switches, it is an object of the present invention to provide a modular architecture for a very large packet switch, which architecture utilizes modules that operate independently of each other. More particularly, it is an object of the present invention to provide a very large packet switch constructed from a plurality of modules which can be synchronized independently and which are of relatively simple construction for ease of maintenance and high reliability.